Lưu Hắc Thát sau đó tham gia nổi dậy chống lại triều đình Tùy, thoạt đầu ông theo Hác Hiếu Đức (郝孝德), sau đó gia nhập vào Ngõa Cương quân của Lý Mật. Sau khi Lý Mật bại trận trước tướng Tùy Vương Thế Sung vào năm 618, do biết Lưu Hắc Thát dũng mãnh nên Vương Thế Sung đã cho Lưu làm kị tướng.

Sau khi Vương Thế Sung buộc Dương Đồng phải thiện nhượng cho mình, lập ra nước Trịnh, Lưu Hắc Thát phụng sự cho Trịnh, được giao trấn thủ Tân Hương (新鄉, nay thuộc Tân Hương, Hà Nam). Theo "Đường thư- quyển 55" thì ông bị tướng Hạ Từ Thế Tích bắt đưa đến chỗ Đậu Kiến Đức, song theo các chú giải Đường thư thì ông tự mình chạy đến chỗ Đậu Kiến Đức. Đậu Kiến Đức cho Lưu Hắc Thát làm tướng và phong tước Hán Đông quận công. Đậu Kiến Đức thường phái Lưu Hắc Thát đem quân đi tập kích, và đôi khi thâm nhập vào trong lãnh thổ của đối phương để thu thập thông tin tình báo. Trong thời gian phụng sự Đậu Kiến Đức, Lưu Hắc Thát đã giành được nhiều chiến thắng.